This invention relates to the flow steering property of linkable reentrant loops to minimize the average access time by positioning information closer to an output port in a storage structure. More particularly, the invention relates to the use of a linear array of linkabe circulating storage loops for storing a working set of records forming a small subset of the total information utilized by a stored programmed controlled information handling system, the "working set" having a high probability of computer program use in the near future and having a size and content changing only slowly with time.
Broadly, Bonyhard and Nelson at page 308 of the March 1973 issue of the Bell System Technical Journal describe the dynamic reallocation of data in a system of closed loop shift registers. The authors point out how dynamic reallocation of data can be combined with major/minor loop organization so as to optimize memory performance. Included in their description is the use of a process of propagating forward n cycles, removing bits from a channel, closing the gap, propagating backwards n cycles, opening a gap and reinserting information in order to effectuate permutation of information in a channel.
There are numerous prior art structures showing the control of bits among the stages of a shift register. Reference can be made to C. K. Wong et al, "The Anticipatory Control of a Cyclically Permutable Memory", IEEE Transactions on Computers, May 19, 1973, pages 481-488; W. F. Beausoleil, U.S. Pat. 3,670,313; A. V. Aho et al, "Dynamic Memories With Rapid Random and Sequential Access", IEEE Transactions on Computers, March, 1974, at page 272.
It is observed in the Bonyhard reference that there is no ordering of records effectuated by a direct information exchange between adjacent loops. Moreover, in the remaining cited references, the bit-oriented permutations do not optimize permutations and sorts as among plural bit equal-length records, for example.
As suggested above, the location of a record can be exploited to reduce average access time by dynamically positioning the record close to the access mechanism. Relatedly, dynamic positioning has meant data reassignment using a storage hierarchy. Frequently the assumption is that all storage positions are equally accessible. This assumption of equal accessibility is valid for random access memories. However, storage based on shift registers such as magnetic bubbles (Beausoliel, U.S. Pat. No. 3,670,313) and charge coupled technology (W. Anacker, "Possible Uses of Charge Transfer Devices and Magnetic Domain Devices in Memory Hierarchies," IEEE Transaction on Magnetics, September 1971, pages 410-415; W. S. Boyle et al, BSTJ, April 1970, pages 587-593) is strongly affected by geometric factors.
Attention is directed to co-pending U.S. patent application, Ser. No. 556,378, filed on Mar. 7, 1975, entitled "Ladder For Information Processing", filed by Chang, Chen and Tung. In the co-pending case, Chang et al describes an apparatus for dynamically permuting a linear list coupled with fixed-length records. This can be stated less formally as an arrangement with multiple shift register loops linked by dual moded switches. Since each loop has no more than two adjacent, switchably interconnected neighbors, then when the two boundary switches to any given loop are set in the first mode of the fixed-length records circulate wholly within its counterpart loop. When a common boundary switch is set in a second mode, then each fixed-length record flows into an adjacent loop and vis-a-vis. Such a structure has been nominated as a "ladder" or a "ladder network".